package com.frank.code_notes.C02_LinkedList;


import cn.hutool.core.lang.Console;
import com.frank.utils.ListNode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Description 24. 两两交换链表中的节点
 * @Author zhoujr
 * @Data 2024/12/4 20:59
 */
public class L024SwapLinkedListNodes {

    /**
     * @Description cur -> 2 | 2 -> 1 | 1 -> 3
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode cur = dummyHead;
        ListNode temp, nodeFirst, nodeTwo;
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            nodeFirst = cur.next;
            nodeTwo = cur.next.next;
            // cur -> 2
            cur.next = nodeTwo;
            // 2 -> 1
            nodeTwo.next = nodeFirst;
            // 1 -> 3
            nodeFirst.next = temp;
            // 移动到下一轮开始位置
            cur = nodeFirst;
        }
        return dummyHead.next;
    }

    /**
     * @Description cur -> 2 | 1 -> 3 | 2 -> 1
     */
    public static ListNode swapPairsSimply(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode cur = dummyHead, nodeFirst, nodeTwo;
        while (cur.next != null && cur.next.next != null) {
            nodeFirst = cur.next;
            nodeTwo = cur.next.next;
            cur.next = nodeTwo; // cur -> 2
            nodeFirst.next = nodeTwo.next; // 1 -> 3
            nodeTwo.next = nodeFirst; // 2 -> 1
            cur = nodeFirst; // 移动到下次开始位置
        }
        return dummyHead.next;
    }

    /**
     * @Description 递归替换
     */
    public static ListNode swapPairsRecursion(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode next = head.next;
        ListNode res = swapPairsRecursion(next.next);

        next.next = head;
        head.next = res;

        return next;
    }

    /**
     * @Description 递归打印
     */
    public static void linkedPrint(ListNode cur) {
        if (cur != null) {
            Console.log(cur.val);
            linkedPrint(cur.next);
        } else {
            Console.log(">>>>>>>>>>>>>>>>>");
        }
    }

    public static void main(String[] args) {
        ListNode swapPairs = swapPairs(ListNode.toListNode(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5))));
        linkedPrint(swapPairs);
        ListNode simply = swapPairsSimply(ListNode.toListNode(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5))));
        linkedPrint(simply);
        ListNode recursion = swapPairsRecursion(ListNode.toListNode(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5))));
        linkedPrint(recursion);
    }

}
